算術 (arithmetic)
有限公理化可能
公理によって組$ (\N,0,S_{:\N\to\N},+_{:\N\times\N\to\N},\times_{:\N\times\N\to\N})を定める
$ \forall n_{\in\N}(Sn\ne 0)
$ \forall n,m_{\in\N}(Sn=Sm\to n=m)
$ \forall n_{\in\N}(n=0\lor\exist m_{\in\N}(Sm=n))
$ \forall n_{\in\N}(n+0=n)
$ \forall n,m_{\in\N}(n+Sm=S(n+m))
$ \forall n_{\in\N}(n\times 0=0)
$ \forall n,m_{\in\N}(n\times Sm=(n\times m)+n)
公理は組$ (\N,0_{\in\N},1_{\in\N},+_{:\N\times\N\to\N})を定める
$ \forall n_{\in\N}(0\ne n+1)
$ \forall n,m_{\in\N}(x+1=y+1\to x=y)
$ \forall n_{\in\N}(n+0=n)
$ \forall n,m_{\in\N}(n+(m+1)=(n+m)+1)
數學的歸納法の公理圖式$ (\varphi(0)\land\forall n_{\in\N}(\varphi(n)\to\varphi(n+1)))\to\forall n_{\in\N}\varphi(n) 任意の乘法を形式化した一つの論理式は存在しない
$ \forall n,m~nm=mn可換
$ \forall n,m,l~(nm)l=n(ml)結合
$ {\rm One}(n):=\forall m~mn=m
$ \exist 1~{\rm One}(1)
$ \forall n,m({\rm One}(nm)\supset{\rm One}(n)\lor{\rm One}(m))
$ \forall n,m,l(nl=ml\supset n=m)
$ \forall n,m(n^a=m^a\supset n=m)
$ n|m:=\exist l~nl=m。$ nは$ mを割り切る
$ \forall x\exist n_{>0},r(x=nr^l\land\forall m,s(x=ms^l\supset n|m))
$ {\rm Prime}(p):=\neg{\rm One}(p)\land\forall n(n|p\supset({\rm One}(n)\lor n=p))素數
$ \forall n\exist p({\rm Prime}(p)\land\neg(p|n))infinitude of primes
$ {\rm PrimePower}(p,P):={\rm Prime}(p)\land p|P\land\forall q({\rm Prime}(q)\land\neg(q=p)\supset\neg(q|P))
$ \forall,p,P,Q(({\rm PrimePower}(p,P)\land{\rm PrimePower}(p,Q))\supset(P|Q\lor Q|P))
$ {\rm InvAdicAbs}(p,n,P):={\rm PrimePower}(p,P)\land P|n\land\forall Q(({\rm PrimePower}(p,Q)\land Q|n)\supset Q|P)。$ Pis the largest power of$ pdividing$ n
$ \forall p,n({\rm Prime}(p)\supset\exist P(p,n,P))
$ \forall n,m(n=m\equiv\forall p({\rm Prime}({\rm InvAdicAbs}(p,n,P)\land{\rm InvAdicAbs}(p,m,P))))unique factorization
$ \forall p,n,m({\rm Prime}(p)\supset\exist P,Q({\rm InvAdicAbs}(p,n,P)\land{\rm InvAdicAbs}(p,m,Q)\land{\rm InvAdicAbs}(p,nm,PQ)))p-adic absolute value is multiplicative
$ \forall n,m(\forall p({\rm Prime}(p)\supset\exist P,Q({\rm InvAdicAbs}(p,n,P)\land{\rm InvAdicAbs}(p,m,Q)\land P|Q))\supset n|m)if the p-adic valuation of a is less than that of$ mfor every prime$ p, then$ n|m
$ \forall n,m\exist l\forall p({\rm Prime}(p)\supset(((p|n\supset\exist P({\rm InvAdicAbs}(p,m,P)\land{\rm InvAdicAbs}(p,l,P)))\land(p|m\supset p|n)))))deleting from the prime factorization of$ mall primes not dividing$ n
$ \forall n\exist m\forall p({\rm Prime}(p)\supset(\exist P({\rm InvAdicAbs}(p,n,P)\land{\rm InvAdicAbs}(p,m,pP)))\land(p|m\supset p|n))increasing each exponent in the prime factorization of a by 1
$ {\rm AdicAbsDiff}_k(p,n,m):={\rm Prime}(p)\land p|nm\land\exist P,Q({\rm InvAdicAbs}(p,n,P)\land{\rm InvAdicAbs}(p,m,Q)\land Q=p^k P)the largest power of$ pdividing$ mis$ p^ktimes the largest power of$ pdividing$ k
$ \forall n,m\exist l\forall p({\rm Prime}(p)\supset(({\rm AdicAbsDiff}_k(p,n,m)\supset{\rm InvAdicAbs}(p,l,p))\land(p|l\supset{\rm AdicAbsDiff}_k(p,n,m)))),$ k>0product of those primes$ psuch that the largest power of$ pdividing$ mis pn times the largest power of$ pdividing$ n
乘法は實行できるが加法を任意には實行できない
n 階算術の model を$ \cal Nとし、其の理論を$ {\rm Th}({\cal N}):=\{\theta|{\cal N}\vDash\theta\}と書く。眞理述語$ T、卽ち n 階算術の文$ \thetaが妥當か否かをその Gödel 數$ \#\thetaから判定する文$ {\cal N}\vDash T(\#\theta)\iff{\cal N}\vDash\thetaが、n 階算術の文であるとしたら矛盾する$ {\rm Th}({\cal N})\cup\{T\}\vDash\bot。$ T\notin{\rm Th}({\cal N}) 初等函數算術 (EFA (elementary function arithmetic)。指數函數算術)
初等歸納的算術 (elementary recursive arithmetic。ERA)
原始歸納的算術 (primitive recursive arithmetic。PRA)
階層
算術的階層 (arithmetical hierarchy。Kleene hierarchy)$ \Sigma^0_n,$ \Pi^0_n,$ \Delta^0_n
有界量化子のみを含む Peano 算術 (PA)に等價な論理式は$ \Sigma^0_0と$ \Pi^0_0の兩方に屬する。$ \Sigma^0_0=\Pi^0_0=\Delta^0_0 論理式$ \psiが$ \Pi^0_nに屬するならば、$ \exist x_1\dots\exist x_k\psiと等價な論理式は$ \Sigma^0_{n+1}に屬する
論理式$ \psiが$ \Sigma^0_nに屬するならば、$ \forall x_1\dots\forall x_k\psiと等價な論理式は$ \Pi^0_{n+1}に屬する
$ \Sigma^0_nにも$ \Pi^0_nにも屬する論理式は$ \Delta^0_nに屬する
$ \Sigma^0_n,$ \Pi^0_n,$ \Delta^0_nに神託機械$ Aを追加した階層は$ \Sigma^{0,A}_n,$ \Pi^{0,A}_n,$ \Delta^{0,A}_nと書く
解析的階層 (analytical hierarchy)$ \Sigma^1_n,$ \Pi^1_n,$ \Delta^1_n
解析集合 (analytic set)$ {\bf \Sigma}^1_1
射影集合 (projective hierarchy)$ {\bf \Sigma}^1_n
複雜性 class (complexity class)
$ {\sf coNP}
Blum の公理 (Blum axioms)
Blum 複雜性測度 (Blum complexity measure)
複雜性 class$ Aに複雜性 class$ Bの神託機械を追加した複雜性 class を$ A^Bと書く
$ \Delta^{\sf P}_0=\Sigma^{\sf P}_0=\Pi^{\sf P}_0:={\sf P}と定める
$ \Delta^{\sf P}_{n+1}:={\sf P}^{\Sigma^{\sf P}_n}
$ \Sigma^{\sf P}_{n+1}:={\sf NP}^{\Sigma^{\sf P}_n}
$ \Pi^{\sf P}_{n+1}:={\sf coNP}^{\Sigma^{\sf P}_n}
$ \Sigma^{\sf P}_1={\sf NP}
$ \Pi^{\sf P}_1={\sf coNP}